package com.jinan.algorithm.slidingWindow;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;

public class SwindowTest {
    public static void main(String[] args) {

    }

    /**
     * 209. 长度最小的子数组
     * 给定一个含有 n 个正整数的数组和一个正整数 target 。
     * 找出该数组中满足其总和大于等于 target 的长度最小的
     * 子数组
     * [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
     *
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int res = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                res = Math.min(res, right - left + 1);
                sum -= nums[left++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

    /**
     * 713. 乘积小于 k 的子数组
     * 给定一个正整数数组 nums。找出该数组内乘积小于 k 的连续的子数组的个数。
     *
     * @param nums
     * @param k
     * @return
     */
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) {
            return 0;
        }
        int left = 0;
        int prod = 1;
        int ans = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            while (prod >= k) {
                prod /= nums[left++];
            }
            ans += right - left + 1;
        }
        return ans;
    }

    /**
     * 3. 无重复字符的最长子串
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) return 0;
        char[] chars = s.toCharArray();
        int left = 0;
        int ans = 0;
        boolean[] map = new boolean[128];
        for (int right = 0; right < chars.length; right++) {
            char c = chars[right];
            while (map[c]) {
                map[chars[left++]] = false;
            }
            map[c] = true;
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * 1004. 最大连续1的个数 III
     * 给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
     *
     * @param nums
     * @param k
     * @return
     */
    public int longestOnes(int[] nums, int k) {
        int left = 0;
        int zero = 0;
        int ans = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) {
                zero++;
            }
            while (zero > k) {
                if (nums[left] == 0) {
                    zero--;
                }
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * 2958. 最多 K 个重复元素的最长子数组
     * 给你一个整数数组 nums 和一个整数 k ，请你返回 最多 有 k 个元素重复的 最长子数组的长度。
     *
     * @param nums
     * @param k
     * @return
     */
    public int maxSubarrayLength(int[] nums, int k) {
        int left = 0;
        int ans = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int right = 0; right < nums.length; right++) {
            int c = nums[right];
//            map.put(c,map.getOrDefault(c,0)+1);
            map.merge(c, 1, Integer::sum);
            while (map.get(c) > k) {
//                map.put(nums[left],map.get(nums[left])-1);
                map.merge(nums[left], -1, Integer::sum);
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * 2730.找到最长的半重复子字符串
     * 给你一个字符串 s ，请你找到 s 中最长的半重复子字符串（一个字母最多只出现一次）并返回该子字符串的长度。
     * 如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是 半重复的
     *
     * @param s
     * @return
     */
    public int longestSemiRepetitiveSubstring(String s) {
        if (s.isEmpty()) return 0;
        if (s.length() == 1) return 1;
        int left = 0;
        int ans = 0;
        int num = 0;
        for (int right = 1; right < s.length(); right++) {
            if (s.charAt(right) == s.charAt(right - 1)) {
                num++;
            }
            while (num > 1) {
                if (s.charAt(left) == s.charAt(left + 1)) {
                    num--;
                }
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * 2779. 数组的最大美丽值
     * 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
     * 美丽值 定义为：数组中由相等元素组成的最长子序列的长度。
     * tips:对数组排序 找到最大子数组 A[i ...j] 使得 A[j] - A[i] ≤ 2 * k。
     *
     * @param nums
     * @param k
     * @return
     */
    public int maximumBeauty(int[] nums, int k) {
        int left = 0;
        int ans = 0;
        Arrays.sort(nums);
        for (int right = 0; right < nums.length; right++) {
            while (nums[right] - nums[left] > 2 * k) {
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * 2962.统计最大元素出现至少 K 次的子数组 <a href="https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/">...</a>
     * 给你一个整数数组 nums 和一个整数 k ，请你返回 最多 有多少个子数组中 最大元素 出现 至少 k 次。
     *
     * @param nums
     * @param k
     * @return
     */
    public long countSubarrays(int[] nums, int k) {
        int left = 0;
        long ans = 0;
        int maxNum = 0;
        int count = 0;
        for (int num : nums) {
            maxNum = Math.max(maxNum, num);
        }
        for (int num : nums) {
            if (num == maxNum) {
                count++;
            }
            while (count == k) {
                if (nums[left] == maxNum) {
                    count--;
                }
                left++;
            }
            ans += left;
        }
        return ans;
    }

    /**
     * 2302. 统计得分小于 K 的子数组数目 <a href="https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/">...</a>
     * 一个数组的 分数 定义为数组之和 乘以 数组的长度。
     * 给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。
     * 子数组 是数组中的一个连续元素序列。
     *
     * @param nums
     * @param k
     * @return
     */
    public long countSubarrays(int[] nums, long k) {
        int left = 0;
        long ans = 0L;
        long sum = 0L;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum * (right - left + 1) >= k) {
                sum -= nums[left];
                left++;
            }
            ans += right - left + 1;
        }
        return ans;
    }

    /**
     * 1658. 将 x 减到 0 的最小操作数 <a href="https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/">...</a>
     * 给你一个整数数组 nums 和一个整数 x 。
     * 每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。
     * 请注意，需要 修改 数组以供接下来的操作使用。
     * 如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
     * tips: 把问题转换成「从 nums 中移除一个最长的子数组，使得剩余元素的和为 x」
     *
     * @param nums
     * @param x
     * @return
     */
    public int minOperations(int[] nums, int x) {
        int target = Arrays.stream(nums).sum() - x;
        if (target < 0) return -1;
        int ans = -1;
        int left = 0;
        int sum = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum > target) {
                sum -= nums[left];
                left++;
            }
            if (sum == target) {
                ans = Math.max(ans, right - left + 1);
            }
        }
        return ans == -1 ? -1 : nums.length - ans;
    }

    /**
     * 76. 最小覆盖子串 <a href="https://leetcode.cn/problems/minimum-window-substring/">...</a>
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     * 注意：
     * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
     * tips:滑动窗口
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        int left = 0;
        String ans = "";
        Map<Character,Integer> map = new HashMap<>();
        map.putAll(t.chars().boxed().collect(Collectors.toMap(c->(char)c.intValue(), c->1,Integer::sum)));
        for (int right=0;right<s.length();right++){
            char c = s.charAt(right);
            if(map.containsKey(c)){
                map.merge(c,-1,Integer::sum);
            }else continue;
            while(map.values().stream().allMatch(v->v<=0)){
                if(ans.isEmpty() ||right-left+1<ans.length()){
                    ans = s.substring(left,right+1);
                }
                char c1 = s.charAt(left);
                if(map.containsKey(c1)){
                    map.merge(c1,1,Integer::sum);
                }
                left++;
            }
        }
        return ans;
    }
    public String minWindow2(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) return "";

        Map<Character, Integer> need = new HashMap<>(); // 需要的字符
        Map<Character, Integer> window = new HashMap<>(); // 窗口中的字符

        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0; // 当前窗口中满足要求的字符数量
        int start = 0;
        int len = Integer.MAX_VALUE;

        while (right < s.length()) {
            char c = s.charAt(right);
            right++;

            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c) <= need.get(c)) {
                    valid++;
                }
            }

            // 收缩窗口
            while (valid == t.length()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                char d = s.charAt(left);
                left++;

                if (need.containsKey(d)) {
                    if (window.get(d).intValue() == need.get(d).intValue()) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    /**
     * 560. 和为 K 的子数组 <a href="https://leetcode.cn/problems/subarray-sum-equals-k/">...</a>
     * 难度: 中等
     * tag: 数组 哈希表 前缀和
     * description: 给你一个整数数组 nums 和一个整数k ，请你统计并返回 该数组中和为k的连续子数组的个数。
     * 提示：
     * 1 <= nums.length <= 2 * 104
     * -1000 <= nums[i] <= 1000
     * -107 <= k <= 107
     * @param nums 数组
     * @param k 目标值
     * @return 连续子数组的个数
     */
    public int subarraySum(int[] nums, int k) {
        int ans = 0;
        int n= nums.length;
        int[] pre=new int[n+1];
        pre[0]=0;
        for (int i=0;i<n;i++){
            pre[i+1]=pre[i]+nums[i];
        }
        // 方法1：枚举所有子数组
        for (int i=0;i<n;i++){
            for (int j=i+1;j<=n;j++){
                //问题转换为找前缀和数组中所有sj-si=k的位置
                if (pre[j]-pre[i]==k){
                    ans++;
                }
            }
        }

        //方法2：哈希表  找sj-si=k等价于找sj=si+k，可以使用哈希表记录si，如果sj-k在哈希表中，则说明存在sj=si+k，即sj-si=k
        Map<Integer,Integer> map=new HashMap<>(n+2);
        for (int sj : pre){
            ans+=map.getOrDefault(sj-k,0);
            map.put(sj,map.getOrDefault(sj,0)+1);
        }
        return ans;
    }


    /**
     * 189. 旋转数组 <a href="https://leetcode.cn/problems/rotate-array/">...</a>
     * 难度: 中等
     * tag: 数组 数学 双指针
     * description: 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数
     * 提示：
     * 1 <= nums.length <= 10^5
     * -2^31 <= nums[i] <= 2^31 - 1
     * 0 <= k <= 10^5
     * @param nums 数组
     * @param k 移动的位数
     */
    public void rotate(int[] nums, int k) {
        // 方法1：数组拷贝
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[(i + k) % nums.length] = nums[i];
        }
        System.arraycopy(ans, 0, nums, 0, nums.length);

        // 方法2：反转
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }


    /**
     * 238. 除自身以外数组的乘积 <a href="https://leetcode.cn/problems/product-of-array-except-self/">...</a>
     * 难度: 中等
     * tag: 数组 前缀和
     * description: 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
     * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
     * 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
     * 提示：
     * 2 <= nums.length <= 10^5
     * -30 <= nums[i] <= 30
     * 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内
     * @param nums 整数数组
     * @return answer 乘积数组
     */
    public int[] productExceptSelf(int[] nums) {
        // 方法1：前缀和+后缀和
        int n = nums.length;
        int[] ans=new int[n];
        int[] pre=new int[n];
        int[] suf=new int[n];
        pre[0]=1;
        suf[n-1]=1;
        for (int i=1;i<n;i++){
            pre[i]=pre[i-1]*nums[i-1];
        }
        for (int i=n-2;i>=0;i--){
            suf[i]=suf[i+1]*nums[i+1];
        }
        for (int i=0;i<n;i++){
            ans[i]=pre[i]*suf[i];
        }
        return ans;
    }
    public int[] productExceptSelf2(int[] nums) {
        //方法2：空间优化
        int n = nums.length;
        int[] ans=new int[n];
        int temp=1;
        for (int i=0;i<n;i++){
            ans[i]=temp;
            temp*=nums[i];
        }
        temp=1;
        for (int i=n-1;i>=0;i--){
            ans[i]*=temp;
            temp*=nums[i];
        }
        return ans;
    }
}
